package com.tgy.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author: tgy
 * @Date: 12/22/20 3:41 PM
 */
public class _103_二叉树的锯齿形层序遍历 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        List<List<Integer>> rets = new ArrayList<>();

        if (root == null) {

            return rets;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        List<Integer> container = new ArrayList<Integer>();
        int count = 1,level = 1;
        while (!queue.isEmpty()) {

            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {

                queue.offer(node.right);
            }

            count--;
            if ((level & 1) == 0) {

                container.add(0,node.val);
            }else {

                container.add(node.val);
            }
            if (count == 0) {

                level++;
                rets.add(container);
                container = new ArrayList<>();
                count = queue.size();
            }
        }

        return rets;
    }
}
